public class ReverseList {
    static class  ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
//  迭代方法
    public static ListNode iterate(ListNode head) {
        ListNode prev=null,next,curr=head;
        while(curr!=null){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        return prev;
    }
//  递归方法
    public static ListNode recursion(ListNode head){

        if(head==null||head.next==null){
            return head;
        }

        ListNode newhead = recursion(head.next);
        head.next.next=head;
        head.next=null;


        return newhead;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);

        ListNode prev =recursion(node1);
        System.out.println(prev);

    }
}
